package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class BinaryTreeLevelOrderTraversal {
	
	//方法一：DFS
    public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> result = new ArrayList<>();
    	levelOrder(root, 0, result);
        return result;
    }
    
    private void levelOrder(TreeNode node, int level, List<List<Integer>> result) {
    	if(node == null) return;
    	
    	if(level == result.size()) {
    		List<Integer> temp = new ArrayList<>();
    		temp.add(node.val);
    		result.add(temp);
    	}else {
    		result.get(level).add(node.val);
    	}
    	
    	levelOrder(node.left, level + 1, result);
    	levelOrder(node.right, level + 1, result);
    	
    }

    //方法二：BFS
	public List<List<Integer>> levelOrder2(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		if(root == null) return result;
		
		LinkedList<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		
		while(!queue.isEmpty()) {
			List<Integer> temp = new ArrayList<>();
			
			for(int size = queue.size(); size > 0; size--) {
				TreeNode node = queue.poll();
				temp.add(node.val);
				
				if(node.left != null)
					queue.offer(node.left);
				
				if(node.right != null)
					queue.offer(node.right);
			}
			
			result.add(temp);
		}
		
		return result;
	}
    
}
